#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include "array.h"
#include "sort.h"
#include "pthread.h"

#if ALGORITHM == 0
struct timespec start_global, stop_global;

typedef struct
{
  int id;
  int start;
  int end;
  int level;
  struct array array;
} thread_info_msort;

pthread_t thread[NB_THREADS];
struct timespec thread_start[NB_THREADS], thread_stop[NB_THREADS];

void merge(struct array * res_array,struct array * array, int start_left, int end_left,
	   int start_right, int end_right){

  int cnt = 0;    
  while (((end_left-start_left) >= 0) &&((end_right-start_right) >= 0)){
    if (array->data[start_left] <= array->data[start_right]){
      res_array->data[cnt] = array->data[start_left];
      start_left++;
    }else{
      res_array->data[cnt] = array->data[start_right];
      start_right++;
    }
    cnt++;
  }
  if ((end_left-start_left) >= 0){
    memcpy((void *)res_array->data+cnt*sizeof(int),&array->data[start_left],
	   (end_left-start_left+1)*sizeof(int));
  }else if ((end_right-start_right) >= 0){
    memcpy((void *)res_array->data+cnt*sizeof(int),&array->data[start_right],
	   (end_right-start_right+1)*sizeof(int));
  }
  return;
}


void seq_merge_sort(struct array * array, int start, int end){
  if ((end - start) < 1){
    return;
  }
  int middle = (end-start)/2;
  
  seq_merge_sort(array,start,start+middle); //Left
  seq_merge_sort(array,start+middle+1,end); //Right
  if (array->data[start+middle] <= array->data[start+middle+1]){
    return;
  }

  struct array *res_array;
  res_array = array_alloc(end-start+1);
  merge(res_array,array,start,start+middle,start+middle+1,end);
  memcpy((void *)array->data+start*sizeof(int),res_array->data,(end-start+1)*sizeof(int));
  free(res_array);
  return;
}

int
get_next_thread_id(int id, int level) {
  switch (id) 
    {
    case 0: 
      if ((level == 0) && (NB_THREADS > 1)) {
	return 1;
      } else if ((level == 1) && (NB_THREADS > 2)) {
	return 2;
      } else if ((level == 2) && (NB_THREADS > 4)) {
	return 4;
      } else {
	return -1;
      }
      break;
    case 1:
      if ((level == 1) && (NB_THREADS > 3)) {
	return 3;
      } else if ((level == 2) && (NB_THREADS > 6)) {
	return 6;
      } else {
	return -1;
      }
    case 2:
      if ((level < 3) && (NB_THREADS > 5)) {
	return 5;
      } else {
	return -1;
      }    
    case 3:
      if ((level < 3) && (NB_THREADS > 7)) {
	return 7;
      } else {
	return -1;
      }
      break;
    default :
      return -1;
    }
} 

static void* 
par_merge_sort(void* arg) {
  thread_info_msort *args;
  args = (thread_info_msort*) arg;

  // Check if end
  if ((args->end - args->start) < 1){
    return NULL;
  }
  thread_info_msort thread_info[2];
  int middle = (args->end-args->start)/2;

  // Check if to spawn more threads
  int next_thread_id = get_next_thread_id(args->id, args->level);
  //printf("Thread: %d, Next_to_spawn: %d\n", args->id ,next_thread_id);
  
  // Right branch
  thread_info[1].start = args->start+middle+1;
  thread_info[1].end = args->end;
  thread_info[1].level = args->level + 1;
  thread_info[1].array = args->array;
  if (next_thread_id != -1) {
    thread_info[1].id = next_thread_id;
    clock_gettime(CLOCK_MONOTONIC, &thread_start[next_thread_id]);
    pthread_create(&thread[next_thread_id], NULL, par_merge_sort, (void*) &thread_info[1]);
  } else {
    thread_info[1].id = args->id;
    par_merge_sort((void *) &thread_info[1]);
  }

  // Left branch
  thread_info[0].id = args->id;
  thread_info[0].start = args->start;
  thread_info[0].end = args->start+middle;
  thread_info[0].level = args->level + 1;
  thread_info[0].array = args->array;
  par_merge_sort((void *) &thread_info[0]);
  
  //printf("Thread: %d, Level: %d\n", args->id, args->level);
  if (next_thread_id != -1) {
    pthread_join(thread[next_thread_id], NULL);
    clock_gettime(CLOCK_MONOTONIC, &thread_stop[next_thread_id]);
  }

  struct array *res_array;
  struct array *arr;
  arr = &args->array;

  if (arr->data[args->start+middle] <= arr->data[args->start+middle+1]){
    return NULL;
  }

  res_array = array_alloc(args->end-args->start+1);
  merge(res_array,&args->array,args->start,args->start+middle,args->start+middle+1,args->end);
  memcpy((void *)arr->data+args->start*sizeof(int),res_array->data,(args->end-args->start+1)*sizeof(int));
  free(res_array);

  return NULL;
}

int sort(struct array * array, int try)
{
  // Start global measurement
  clock_gettime(CLOCK_MONOTONIC, &start_global); 
#if NB_THREADS == 0
  seq_merge_sort(array, 0, array->length-1);
  
  // End global measurement
  clock_gettime(CLOCK_MONOTONIC, &stop_global); 
  
  printf("%i %i %i %li %i %li %i %li %i %li %i;\n",NB_THREADS, 0, (int) start_global.tv_sec,
	 start_global.tv_nsec, (int) stop_global.tv_sec, stop_global.tv_nsec,
	 (int) start_global.tv_sec, start_global.tv_nsec,
	 (int) stop_global.tv_sec, stop_global.tv_nsec, try);
#else
  thread_info_msort thread_info;
  thread_info.id = 0;
  thread_info.start = 0;
  thread_info.end = array->length-1;
  thread_info.level = 0;
  thread_info.array = *array;
  clock_gettime(CLOCK_MONOTONIC, &thread_start[0]);
  pthread_create(&thread[0], NULL, par_merge_sort, (void*) &thread_info);
  pthread_join(thread[0], NULL);
  clock_gettime(CLOCK_MONOTONIC, &thread_stop[0]);

  // End global measurement
  clock_gettime(CLOCK_MONOTONIC, &stop_global);

  int i;
  for (i = 0; i < NB_THREADS; i++)
    {
      printf("%i %i %i %li %i %li %i %li %i %li %i;\n",NB_THREADS, i + 1, (int) start_global.tv_sec,
	     start_global.tv_nsec, (int) stop_global.tv_sec, stop_global.tv_nsec,
	     (int) thread_start[i].tv_sec, thread_start[i].tv_nsec,
	     (int) thread_stop[i].tv_sec, thread_stop[i].tv_nsec, try);
    }
#endif
  return 0;
}
#endif

#if ALGORITHM == 1
struct timespec start_global, stop_global;

void 
seq_sample_sort(struct array * array, int start, int end){
  // is basically an inplace quicksort

  if (start < end){
    int pivot_index = (start+end)/2;
    int pivot_value = array->data[pivot_index];
    int store_index = start;
    int i, tmp;
    
    // Partition the array
    tmp = array->data[end];
    array->data[end] = pivot_value;
    array->data[pivot_index] = tmp;
    for(i = start; i < end; i++){
      if (array->data[i] < pivot_value){
	tmp = array->data[i];
	array->data[i] = array->data[store_index];
	array->data[store_index] = tmp;
	store_index++;
      }
    }
    
    tmp = array->data[end];
    array->data[end] = array->data[store_index];
    array->data[store_index] = tmp;
    
    // Recursive calls
    seq_sample_sort(array,start,store_index - 1);
    seq_sample_sort(array,store_index + 1,end);
  }
}


#if NB_THREADS > 0
int pivots[NB_THREADS-1];
pthread_barrier_t barrier;
struct timespec thread_start[NB_THREADS], thread_stop[NB_THREADS];

// First index: Thread ID
// Second index: Bucket
// Third index: Element in bucket  
int ***bucket_array;
int bucket_cnt[NB_THREADS][NB_THREADS];

typedef struct
{
  int id;
  struct array array;
} thread_info;

int
get_bucket_index (int data){
  int i;
  for (i = 0; i < NB_THREADS - 1; i++) {
    //printf("data: %d, pivots[i]: %d\n", data, pivots[i]);
    if (data < pivots[i]) {
      return i;
    }
  }
  return i;
}

static void*
partition_sub_array(void* arg) {

  int i,j;
  thread_info *args;
  args = (thread_info*) arg;
  struct array array = args->array;

  // Start thread measurement
  clock_gettime(CLOCK_MONOTONIC, &thread_start[args->id]);

  // Create indexes
  int start_index = args->id*array.length/NB_THREADS;
  int end_index = (args->id == NB_THREADS-1) ? array.length : 
    ((args->id+1)*array.length/NB_THREADS);

  // Place value in correct sub array
  if (NB_THREADS > 1) {
    for (i = start_index; i < end_index; i++) {
      int bucket_index = get_bucket_index(array.data[i]);
      bucket_array[args->id][bucket_index][bucket_cnt[args->id][bucket_index]] = array.data[i];
      /*printf("Value: %d, in thread: %d, in bucket: %d, in element: %d\n", 
	   bucket_array[args->id][bucket_index][bucket_cnt[args->id][bucket_index]],
	   args->id, bucket_index, bucket_cnt[args->id][bucket_index]);*/
      bucket_cnt[args->id][bucket_index]++;
    }
  }
  
  // Sync all threads
  pthread_barrier_wait(&barrier);

  // Calculate start and end index in array
  if (NB_THREADS > 1) {
    start_index = 0;
    end_index = -1; 
    for (i = 0; i < args->id; i++) {
      for (j = 0; j < NB_THREADS; j++) {
	start_index += bucket_cnt[j][i]; 
	end_index += bucket_cnt[j][i]; 
      }
    }
    for (j = 0; j < NB_THREADS; j++) {
      end_index += bucket_cnt[j][i]; 
    }
  }

  // Append sublists (in every thread) and perform in-place quicksort on the new list
  int offset = 0;
  if (NB_THREADS > 1) {
    for (i = 0; i < NB_THREADS; i++) {
      memcpy((void*)array.data + sizeof(int)*(start_index+offset), &bucket_array[i][args->id][0], sizeof(int)*bucket_cnt[i][args->id]);
      //printf("Thread: %d, Start value: %d, cnt: %d, index: %d\n", args->id, bucket_array[i][args->id][0], bucket_cnt[i][args->id], start_index+offset);
    offset += bucket_cnt[i][args->id];
    }
  }
  
  // Sort array sequentially in every thread
  seq_sample_sort(&array, start_index, end_index);

  // Start thread measurement
  clock_gettime(CLOCK_MONOTONIC, &thread_stop[args->id]);
  
  return NULL;
}

int sort(struct array * array, int try)
{
  int i, j, tmp;
  // Start global measurement
  clock_gettime(CLOCK_MONOTONIC, &start_global);

  // Init bucket_array
  if (NB_THREADS > 1) {
    bucket_array = malloc(sizeof(int)*NB_THREADS); 
    for (i = 0; i < NB_THREADS; i++) { 
      bucket_array[i] = malloc(sizeof(int)*NB_THREADS); 
    }
    for (i = 0; i < NB_THREADS; i++) {
      for (j = 0; j < NB_THREADS; j++) {
	bucket_array[i][j] = malloc(sizeof(int)*((array->length)/(NB_THREADS-1))); 
      }
    }
  }
  
  // Create pivots
  //printf("Array length: %d\n", array->length);
  int p_factor = array->length/1000;
  int pivots_cand[(NB_THREADS-1)*p_factor];
  for (i = 0; i < p_factor*(NB_THREADS-1)-1; i++) {
    pivots_cand[i] = array->data[(i+1) * (array->length/(NB_THREADS*p_factor))];
    //printf("pivot index: %d, pivot value: %d\n", i, pivots[i]);
  }
  
  // Sort pivot values, bubblesort
  struct array *piv;
  piv->length = (NB_THREADS-1)*p_factor;
  piv->data = pivots_cand;
  seq_sample_sort(piv, 0, piv->length-1);

  for (i=0; i<NB_THREADS-1; i++) {
    pivots[i] = pivots_cand[i*p_factor+p_factor/2];
    //printf("pivot index: %d, pivot value: %d\n", i, pivots[i]);
  }
  
  pthread_t thread[NB_THREADS];
  thread_info thread_info[NB_THREADS];

  // Create and execute threads
  pthread_barrier_init(&barrier, NULL, NB_THREADS);
  for (i = 0; i < NB_THREADS; i++)
    {
      thread_info[i].id = i;
      thread_info[i].array = *array; 
      pthread_create(&thread[i], NULL, partition_sub_array, (void*) &thread_info[i]);
    }
  
  // Synchronize threads
  for (i = 0; i < NB_THREADS; i++)
    {
      pthread_join(thread[i], NULL);
    }

  // End global measurement
  clock_gettime(CLOCK_MONOTONIC, &stop_global);

  for (i = 0; i < NB_THREADS; i++)
    {
      printf("%i %i %i %li %i %li %i %li %i %li %i;\n",NB_THREADS, i + 1, (int) start_global.tv_sec,
	     start_global.tv_nsec, (int) stop_global.tv_sec, stop_global.tv_nsec,
	     (int) thread_start[i].tv_sec, thread_start[i].tv_nsec,
	     (int) thread_stop[i].tv_sec, thread_stop[i].tv_nsec, try);
    }

  // Free Resources
  if (NB_THREADS > 1) {
    for (i = 0; i < NB_THREADS; i++) {
      for (j = 0; j < NB_THREADS; j++) {
	free(bucket_array[i][j]);
      }
    }
    for (i = 0; i < NB_THREADS; i++) {
      free(bucket_array[i]);
    }
    free(bucket_array);
  }

  return 0;
}

#else

// Sequential sort
int sort(struct array * array, int try)
{
  int i;

  // Start global measurement
  clock_gettime(CLOCK_MONOTONIC, &start_global);

  seq_sample_sort(array,0,array->length - 1);

  // End global measurement
  clock_gettime(CLOCK_MONOTONIC, &stop_global); 

  printf("%i %i %i %li %i %li %i %li %i %li %i;\n",NB_THREADS, 0, (int) start_global.tv_sec,
	 start_global.tv_nsec, (int) stop_global.tv_sec, stop_global.tv_nsec,
	 (int) start_global.tv_sec, start_global.tv_nsec,
	 (int) stop_global.tv_sec, stop_global.tv_nsec, try);
  return 0;
}

#endif

#endif
